package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

import java.util.Arrays;

/**
 * @ClassName Medium_33_SearchRotatedSortedArray
 * @Description Medium_33_SearchRotatedSortedArray
 * @Author wanghaiwei
 * @Date 2023/2/13 15:07
 */
public class Medium_33_SearchRotatedSortedArray {
    public int search(int[] nums, int target) {
        return searchInRotatedArray(nums, target, 0, nums.length - 1);
    }

    private int searchInRotatedArray(int[] nums, int target, int leftIdx, int rightIdx) {
        int midIdx = (leftIdx + rightIdx) / 2;
        if (nums[midIdx] == target) {
            return midIdx;
        }
        if (leftIdx == rightIdx) {
            return nums[leftIdx] == target ? leftIdx : -1;
        }
        //如果当前递归的子数组，是有序的，那么直接遵循二分查找的逻辑执行
        if (nums[leftIdx] < nums[rightIdx]) {
            //如果目标值可能存在于有序数组中，才进行二分法，不然就直接返回-1，这样可以省点时间
            if (nums[rightIdx] < target || nums[leftIdx] > target) {
                return -1;
            } else {
                return Math.max(Arrays.binarySearch(nums, leftIdx, rightIdx + 1, target), -1);
            }
        } else {
            //如果当前子数组，非有序，那么就继续"二分"
            int result = searchInRotatedArray(nums, target, leftIdx, midIdx);
            if (result != -1) {
                return result;
            }
            result = searchInRotatedArray(nums, target, midIdx + 1, rightIdx);
            if (result != -1) {
                return result;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Medium_33_SearchRotatedSortedArray solution = new Medium_33_SearchRotatedSortedArray();
        int result = solution.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0);
        Assert.isTrue(4 == result, "4,5,6,7,0,1,2 -> 0计算错误，预期：4，实际：" + result);
        result = solution.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3);
        Assert.isTrue(-1 == result, "4,5,6,7,0,1,2 -> 3计算错误，预期：-1，实际：" + result);
        result = solution.search(new int[]{1}, 0);
        Assert.isTrue(-1 == result, "1 -> 0计算错误，预期：-1，实际：" + result);
        result = solution.search(new int[]{1}, 1);
        Assert.isTrue(0 == result, "1 -> 0计算错误，预期：0，实际：" + result);
        result = solution.search(new int[]{3, 4, 5, 6, 1, 2}, 2);
        Assert.isTrue(5 == result, "3,4,5,6,1,2 -> 2计算错误，预期：5，实际：" + result);
    }
}
